There are many applications wherein an electronic device needs a non-volatile non-decreasing counter. For example, such a counter may be needed to keep track of the amount of usage of the device. For example, for warranty reasons one may want to keep track of how often the device was powered-up. Another reason for having a non-volatile non-decreasing counter is for security purposes. For example, patent application US 2010/0318786, with title ‘Trusted Hardware Component for Distributed Systems’, included by reference, discloses a trusted hardware component comprising a monotonically non-decreasing counter. Other applications of non-decreasing counters include avoiding roll-back attacks in which an attacker attempts to roll-back the entire device to a previous state, for example, to prolong access to content under a digital right.
One particular aspect of implementing counters in non-volatile memory, in particular EEPROM memory, is that the memory may have restrictions on the number of program-erase cycles it supports.
A typical realization of a counter that stores its value in a non-volatile memory would be a binary counter. A binary counter has the advantage of needing the least number of bits to support a particular counting range. Counting up to 2^n−1 needs only n bits of memory cells. On the other hand, using the binary representation, the least significant bit toggles on every increment of the counter. This leads to a very high number of cycles in the least-significant bits in the EEPROM which could exceed the endurance of the EEPROM. (The endurance is the number of cycles an EEPROM memory cell can be programmed and then erased until end of life time of the cell). Malfunctioning devices are likely, especially for larger values of n.
A little better approach than a binary counter value would be to use a Gray code where the bit coding is done so that from one counter state to the next only one bit changes (not always the least significant bit). This would distribute the number of cycles a little bit better but in total the number of cycles compared to the number of memory cells used remains very high. Even if so-called balanced gray codes are used, in which bit changes are distributed uniformly over the bits, the number of bit changes will eventually exceed endurance for larger values of n.
Very complicated methods are used for wear-leveling in complex systems like flash memories. These methods require very high effort on encoding and are only useful for complex file systems. The basic concept there is that “damaged” memory cells are relocated to other memory areas.
U.S. Pat. No. 5,231,592 discloses a known counter implemented on electrically erasable and programmable read-only memory (EEPROM). The EEPROM, which has an endurance of ‘V’, i.e., each cell is designed to be erased and programmed at most V times. The EEPROM is divided into N count areas which store count values in binary representation, each count are capable of storing count values from zero to V, and a number area for storing a number in binary representation identifying the count area currently in use. The count areas are used in succession to store counts up to N times V, with a maximum of V^2.